package Ch_3_2_Binary_Search_Trees;

import edu.princeton.cs.algs4.StdOut;

public class Practise_3_2_08 {
    public static int optCompares(int N) {
        // 计算有多少层
        int sum = 0, levels = 0;
        while (true) { 
            sum += (1 << levels);
            if (sum > N) break;
            levels++;
        }
        sum -= (1 << levels);
        StdOut.print("   " + levels + "   " + sum + "  ");
        
        // 计算内部路径长度
        int internal = 0;
        for (int i = 0; i < levels; i++)
            internal += i * (1 << i);
        internal += (N - sum) * levels;
        
        return internal / N;
    }
    public static void main(String[] args) {
        for (int N = 2; N < 100; N++) {
            StdOut.printf("规模为 %d 的满二叉树随机查找命中的平均比较次数为 : %d\n",
                    N, optCompares(N));
        }
    }
    // output
    /*
     *     1   1  规模为 2 的满二叉树随机查找命中的平均比较次数为 : 0
           2   3  规模为 3 的满二叉树随机查找命中的平均比较次数为 : 0
           2   3  规模为 4 的满二叉树随机查找命中的平均比较次数为 : 1
           2   3  规模为 5 的满二叉树随机查找命中的平均比较次数为 : 1
           2   3  规模为 6 的满二叉树随机查找命中的平均比较次数为 : 1
           3   7  规模为 7 的满二叉树随机查找命中的平均比较次数为 : 1
           3   7  规模为 8 的满二叉树随机查找命中的平均比较次数为 : 1
           3   7  规模为 9 的满二叉树随机查找命中的平均比较次数为 : 1
           3   7  规模为 10 的满二叉树随机查找命中的平均比较次数为 : 1
           3   7  规模为 11 的满二叉树随机查找命中的平均比较次数为 : 2
           3   7  规模为 12 的满二叉树随机查找命中的平均比较次数为 : 2
           3   7  规模为 13 的满二叉树随机查找命中的平均比较次数为 : 2
           3   7  规模为 14 的满二叉树随机查找命中的平均比较次数为 : 2
           4   15  规模为 15 的满二叉树随机查找命中的平均比较次数为 : 2
           4   15  规模为 16 的满二叉树随机查找命中的平均比较次数为 : 2
           4   15  规模为 17 的满二叉树随机查找命中的平均比较次数为 : 2
           4   15  规模为 18 的满二叉树随机查找命中的平均比较次数为 : 2
           4   15  规模为 19 的满二叉树随机查找命中的平均比较次数为 : 2
           4   15  规模为 20 的满二叉树随机查找命中的平均比较次数为 : 2
           4   15  规模为 21 的满二叉树随机查找命中的平均比较次数为 : 2
           4   15  规模为 22 的满二叉树随机查找命中的平均比较次数为 : 2
           4   15  规模为 23 的满二叉树随机查找命中的平均比较次数为 : 2
           4   15  规模为 24 的满二叉树随机查找命中的平均比较次数为 : 2
           4   15  规模为 25 的满二叉树随机查找命中的平均比较次数为 : 2
           4   15  规模为 26 的满二叉树随机查找命中的平均比较次数为 : 3
           4   15  规模为 27 的满二叉树随机查找命中的平均比较次数为 : 3
           4   15  规模为 28 的满二叉树随机查找命中的平均比较次数为 : 3
           4   15  规模为 29 的满二叉树随机查找命中的平均比较次数为 : 3
           4   15  规模为 30 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 31 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 32 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 33 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 34 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 35 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 36 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 37 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 38 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 39 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 40 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 41 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 42 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 43 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 44 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 45 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 46 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 47 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 48 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 49 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 50 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 51 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 52 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 53 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 54 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 55 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 56 的满二叉树随机查找命中的平均比较次数为 : 3
           5   31  规模为 57 的满二叉树随机查找命中的平均比较次数为 : 4
           5   31  规模为 58 的满二叉树随机查找命中的平均比较次数为 : 4
           5   31  规模为 59 的满二叉树随机查找命中的平均比较次数为 : 4
           5   31  规模为 60 的满二叉树随机查找命中的平均比较次数为 : 4
           5   31  规模为 61 的满二叉树随机查找命中的平均比较次数为 : 4
           5   31  规模为 62 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 63 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 64 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 65 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 66 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 67 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 68 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 69 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 70 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 71 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 72 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 73 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 74 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 75 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 76 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 77 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 78 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 79 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 80 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 81 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 82 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 83 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 84 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 85 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 86 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 87 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 88 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 89 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 90 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 91 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 92 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 93 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 94 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 95 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 96 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 97 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 98 的满二叉树随机查找命中的平均比较次数为 : 4
           6   63  规模为 99 的满二叉树随机查找命中的平均比较次数为 : 4
     */
}
